﻿using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Solution
{
    public class TreeNode
    {
        public int val;
        public TreeNode left;
        public TreeNode right;
        public TreeNode(int val = 0, TreeNode left = null, TreeNode right = null)
        {
            this.val = val;
            this.left = left;
            this.right = right;
        }


        /// <summary>
        /// leetcode  654  最大二叉树
        /// </summary>
        /// <param name="nums"></param>
        /// <returns></returns>
        public TreeNode ConstructMaximumBinaryTree(int[] nums)
        {
            return MaximumBinaryTreeHelper(nums, 0, nums.Length - 1);
        }

        TreeNode MaximumBinaryTreeHelper(int[] nums, int start, int end)
        {
            if (start > end) return null;
            int maxIndex = start;
            for (int i = start; i <= end; i++)
            {
                if (nums[i] > nums[maxIndex])
                {
                    maxIndex = i;
                }
            }
            TreeNode root = new TreeNode(nums[maxIndex]);
            root.left = MaximumBinaryTreeHelper(nums, start, maxIndex - 1);
            root.right = MaximumBinaryTreeHelper(nums, maxIndex + 1, end);
            return root;
        }

        /// <summary>
        /// leetcode  1261  在受污染的二叉树中查找元素
        /// </summary>
        public class FindElements
        {
            ISet<int> valSet;

            public FindElements(TreeNode root)
            {
                valSet = new HashSet<int>();
                valSet.Add(0);
                root.val = 0;
                Queue<TreeNode> queue = new Queue<TreeNode>();
                queue.Enqueue(root);
                while (queue.Count > 0)
                {
                    TreeNode node = queue.Dequeue();
                    if (node.left != null)
                    {
                        node.left.val = node.val * 2 + 1;
                        valSet.Add(node.val * 2 + 1);
                        queue.Enqueue(node.left);
                    }
                    if (node.right != null)
                    {
                        node.right.val = node.val * 2 + 2;
                        valSet.Add(node.val * 2 + 2);
                        queue.Enqueue(node.right);
                    }
                }
            }

            public bool Find(int target)
            {
                return valSet.Contains(target);
            }
        }


        /// <summary>
        /// leetcode  337  打家劫舍3(动态规划)
        /// </summary>
        /// <param name="root"></param>
        /// <returns></returns>
        public int Rob(TreeNode root)
        {
            // res[0] 表示不偷该节点, res[1] 表示偷该节点
            int[] res = Robber(root);
            return Math.Max(res[0], res[1]);
        }

        public int[] Robber(TreeNode root)
        {
            int[] res = new int[2];
            if (root == null) return res;

            // res[0] = Robber(root.left);
            int[] left = Robber(root.left);
            int[] right = Robber(root.right);

            res[0] = Math.Max(left[0], left[1]) + Math.Max(right[0], right[1]);
            res[1] = root.val + left[0] + right[0];

            return res;
        }

        /// <summary>
        /// leetcode  111  二叉树的最小深度
        /// </summary>
        /// <param name="root"></param>
        /// <returns></returns>
        public int MinDepth(TreeNode root)
        {
            if (root == null)
            {
                return 0;
            }
            if (root.left == null && root.right == null)
            {
                return 1;
            }
            int min1 = MinDepth(root.left);
            int min2 = MinDepth(root.right);

            if (root.left == null || root.right == null)
            {
                return min1 + min2 + 1;
            }
            return Math.Min(min1, min2) + 1;
        }

        /// <summary>
        /// leetcode  515  在每个树行中找最大值
        /// </summary>
        /// <param name="root"></param>
        /// <returns></returns>
        public IList<int> LargestValues(TreeNode root)
        {
            IList<int> res = new List<int>();
            if (root == null)
                return res;
            Queue<TreeNode> queue = new Queue<TreeNode>();
            int levelCount = 0;

            queue.Enqueue(root);
            while (queue.Count > 0)
            {
                levelCount = queue.Count;
                int max = int.MinValue;

                for (int i = 0; i < levelCount; i++)
                {
                    TreeNode node = queue.Dequeue();
                    if (node.val > max)
                        max = node.val;

                    if (node.left != null)
                        queue.Enqueue(node.left);
                    if (node.right != null)
                    {
                        queue.Enqueue(node.right);
                    }
                }
                res.Add(max);
            }
            return res;
        }



        /// <summary>
        /// leetcode  637  二叉树的层平均值
        /// </summary>
        /// <param name="root"></param>
        /// <returns></returns>
        public IList<double> AverageOfLevels(TreeNode root)
        {
            IList<double> res = new List<double>();
            if (root == null)
            {
                return res;
            }
            Queue<TreeNode> queue = new Queue<TreeNode>();
            queue.Enqueue(root);
            int levelCount = 0;
            while (queue.Count > 0)
            {
                levelCount = queue.Count;
                double sum = 0;
                for (int i = 0; i < levelCount; i++)
                {
                    TreeNode node = queue.Dequeue();
                    sum += node.val;
                    if (node.left != null)
                    {
                        queue.Enqueue(node.left);
                    }
                    if (node.right != null)
                    {
                        queue.Enqueue(node.right);
                    }
                }
                res.Add(sum / levelCount);
            }
            return res;
        }

        /// <summary>
        /// leetcode  199  二叉树的右视图
        /// </summary>
        /// <param name="root"></param>
        /// <returns></returns>
        public IList<int> RightSideView(TreeNode root)
        {
            IList<int> res = new List<int>();
            if (root == null)
            {
                return res;
            }
            Queue<TreeNode> queue = new Queue<TreeNode>();
            queue.Enqueue(root);
            int levelCount = 0;
            while (queue.Count > 0)
            {
                levelCount = queue.Count;
                for (int i = 0; i < levelCount; i++)
                {
                    TreeNode node = queue.Dequeue();
                    if (i == levelCount - 1)
                    {
                        res.Add(node.val);
                    }
                    if (node.left != null)
                    {
                        queue.Enqueue(node.left);
                    }
                    if (node.right != null)
                    {
                        queue.Enqueue(node.right);
                    }
                }
            }
            return res;
        }

        /// <summary>
        /// leetcode  102  二叉树的层次遍历
        /// </summary>
        /// <param name="root"></param>
        /// <returns></returns>
        public IList<IList<int>> LevelOrder(TreeNode root)
        {
            IList<IList<int>> res = new List<IList<int>>();
            if (root == null)
                return res;
            Queue<TreeNode> queue = new Queue<TreeNode>();
            int levelCount = 0;

            queue.Enqueue(root);
            while (queue.Count > 0)
            {
                levelCount = queue.Count;
                List<int> levelList = new List<int>();

                for (int i = 0; i < levelCount; i++)
                {
                    TreeNode node = queue.Dequeue();
                    levelList.Add(node.val);

                    if (node.left != null)
                        queue.Enqueue(node.left);
                    if (node.right != null)
                    {
                        queue.Enqueue(node.right);
                    }
                }
                res.Add(levelList);
            }

            return res;
        }

        /// <summary>
        /// leetcode  107  二叉树的层次遍历2
        /// </summary>
        /// <param name="root"></param>
        /// <returns></returns>
        public IList<IList<int>> LevelOrderBottom(TreeNode root)
        {
            IList<IList<int>> res = new List<IList<int>>();
            if (root == null)
                return res;
            Queue<TreeNode> queue = new Queue<TreeNode>();
            int levelCount = 0;

            queue.Enqueue(root);
            while (queue.Count > 0)
            {
                levelCount = queue.Count;
                List<int> levelList = new List<int>();

                for (int i = 0; i < levelCount; i++)
                {
                    TreeNode node = queue.Dequeue();
                    levelList.Add(node.val);

                    if (node.left != null)
                        queue.Enqueue(node.left);
                    if (node.right != null)
                    {
                        queue.Enqueue(node.right);
                    }
                }
                res.Add(levelList);
            }
            res.Reverse();
            return res;
        }




        //TreeNode resNode = null;
        //int maxDepth = 0;
        ///// <summary>
        ///// leetcode  1123  最深叶节点的公共祖先
        ///// </summary>
        ///// <param name="root"></param>
        ///// <returns></returns>
        //public TreeNode LcaDeepestLeaves(TreeNode root)
        //{
        //    DFSDepth(root, maxDepth);
        //    return resNode;
        //}

        //int DFSDepth(TreeNode node, int depth)
        //{
        //    if (node == null)
        //    {
        //        maxDepth = Math.Max(maxDepth, depth);
        //        return depth;
        //    }
        //    int leftDepth = DFSDepth(node.left, depth + 1);
        //    int rightDepth = DFSDepth(node.right, depth + 1);
        //    if (leftDepth == rightDepth && leftDepth == maxDepth)
        //    {
        //        resNode = node;
        //    }
        //    return Math.Max(leftDepth, rightDepth);
        //}
    }
}
